package LearnDataStructure.c_树结构.有序树;

import LearnDataStructure.c_树结构.MyTreeAPI;
import LearnDataStructure.c_树结构.MyTreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-07 14:13
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.有序树
 */
/*

log M   除以  log N
   e            e

等于

log M
   N


Math.log(x)
返回x以e为底的对数，返回数值的类型是double。
Math.floor(x)
向上取整的四舍五入，Math.floor(5.1) = 6


int x = 1 << y
x代表2^y


满二叉树，设根节点算第1层
那么从root到第n层，总共的节点个数是(2^n - 1)个
4层满二叉树的节点是2^4 - 1 = 15个

对于完全二叉树，假设我们利用m个节点制作成满二叉树，最终结果会有

(log m)(对这个对数进行向下取整) + 1   层
(   2 )

log 15 = 3.9.... 即3 + 1 = 4层
   2
 */
public class MyTreeIMPL<E> implements MyTreeAPI<E> {
    private int size = 0;
    private MyTreeNode<E> root = null;

    public MyTreeIMPL(MyTreeNode<E> root) {
        this.root = root;
        size++;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public MyTreeNode<E> getRoot() {
        return root;
    }

    @Override
    public MyTreeNode<E> getParent(MyTreeNode<E> node) {
        return node.parent;
    }

    @Override
    public MyTreeNode<E> getFirstChild(MyTreeNode<E> node) {
        return node.children.get(0);
    }

    @Override
    public MyTreeNode<E> getNextSibling(MyTreeNode<E> node) {
        List<MyTreeNode<E>> children = node.parent.children;
        int index = children.indexOf(node);
        try {
            return children.get(index + 1);
        } catch (Exception e) {
            return null;
        }
    }

    /**
     * DFS
     * @param node
     * @return
     */
    @Override
    public int getHeight(MyTreeNode<E> node) {
        if (node.children == null) {
            return 0;
        } else {
            int h = 0;
            for (int i = 0; i < node.children.size(); i++) {
                h = Math.max(h,getHeight(node.children.get(i)));
            }
            return h + 1;
        }
    }

    /**
     * 返回整棵树的高度
     * @return
     */
    public int getHeight() {
        return getHeight(root);
    }

    @Override
    public void insertChild(MyTreeNode<E> node, MyTreeNode<E> child) {
        if (node.children == null) {
            node.children = new ArrayList<MyTreeNode<E>>();
        }
        node.children.add(child);
        child.parent = node;
        size++;
    }

    @Override
    public void deleteChild(MyTreeNode<E> node, int index) {
        try {
            MyTreeNode<E> targetNode = node.children.get(index);
            int num = partSize(targetNode);
            size = size - num;
            targetNode.parent = null;
            node.children.remove(index);
        } catch (Exception e) {
            return;
        }
    }

    public int partSize(MyTreeNode<E> node) {
        if (node.children == null) {
            return 1;
        } else {
            int size = 1;
            ArrayList<MyTreeNode<E>> list = (ArrayList<MyTreeNode<E>>) node.children;
            for (int i = 0; i < list.size(); i++) {
                size = size + partSize(list.get(i));
            }
            return size;
        }
    }

    @Override
    public List<MyTreeNode<E>> preOrder(MyTreeNode<E> root) {
        List<MyTreeNode<E>> list = new ArrayList<>();
        preOrderDFS(list,root);
        return list;
    }

    public void preOrderDFS(List<MyTreeNode<E>> list, MyTreeNode<E> node) {
        if (node.children == null) {
            list.add(node);
        } else {
            list.add(node);
            List<MyTreeNode<E>> children = node.children;
            for (MyTreeNode<E> child : children) {
                preOrderDFS(list,child);
            }
        }
    }

    @Override
    public List<MyTreeNode<E>> postOrder(MyTreeNode<E> root) {
        List<MyTreeNode<E>> list = new ArrayList<>();
        postOrderDFS(list,root);
        return list;
    }

    public void postOrderDFS(List<MyTreeNode<E>> list, MyTreeNode<E> node) {
        if (node.children == null) {
            list.add(node);
        } else {
            List<MyTreeNode<E>> children = node.children;
            for (MyTreeNode<E> child : children) {
                preOrderDFS(list,child);
            }
            list.add(node);
        }
    }

    @Override
    public List<List<MyTreeNode<E>>> levelOrder(MyTreeNode<E> root) {
        List<List<MyTreeNode<E>>> result = new ArrayList<List<MyTreeNode<E>>>();
        Queue<MyTreeNode<E>> queue = new LinkedList<MyTreeNode<E>>();
        //初始化
        queue.add(root);
        MyTreeNode<E> last = root;
        MyTreeNode<E> next = null;

        //一定有第一行;为第一行做准备
        List<MyTreeNode<E>> currentLine = new ArrayList<MyTreeNode<E>>();
        // firstLine.add(root);这里不添加
        result.add(currentLine);//先加入空行，后面会填入数据

        while (!queue.isEmpty()) {
            MyTreeNode<E> peek = queue.peek();//peek是待出列元素
            if (peek.children != null) {
                for (MyTreeNode<E> child : peek.children) {
                    queue.add(child);
                    next = child;//移动指针；最终next会指向最后一个孩子
                }
            }
            //队列弹出首元素
            MyTreeNode<E> currentFirstElement = queue.poll();
            //代表当前的行的列表currentLine,此时添加出列的元素
            currentLine.add(currentFirstElement);
            if (peek == last && !queue.isEmpty()) {//如果弹出元素就是last指针指向的元素，且队列不为空
                currentLine = new ArrayList<MyTreeNode<E>>();
                result.add(currentLine);//先加入空行，后面会填入数据
                last = next;
            }
        }
        return result;
    }

    public List<List<MyTreeNode<E>>> levelOrder() {
        return levelOrder(root);
    }
}
